#define _CRT_SECURE_NO_WARNINGS 1
#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
using namespace std;
//http://www.oj7.cn/
int n, m, f[5001];
struct node
{
	int wi, vi;
}Goods[5001];
int main()
{
	cin >> m >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> Goods[i].wi >> Goods[i].vi;
	}
	for (int i = 1; i <= n; i++)
	{
		for (int v = m; v > 0; v--)
		{
			if (Goods[i].wi <= v)
			{
				f[v] = max(f[v], f[v - Goods[i].wi] + Goods[i].vi);
			}
		}
	}
	cout << f[m] << endl;

	return 0;
}

